Maximum average subarray II [Math]

Time: O(N); Space: O(N); easy

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4

Output: 12.75

Explanation:

• Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Notes:

• 1 <= K <= N <= 30,000.

• Elements of the given array will be in the range [-10,000, 10,000].

class Solution1(object):
    def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        def getDelta(avg, nums, k):
            accu = [0.0] * (len(nums) + 1)
            minval_pos = None
            delta = 0.0
            for i in range(len(nums)):
                accu[i+1] = nums[i] + accu[i] - avg
                if i >= (k-1):
                    if minval_pos == None or accu[i-k+1] < accu[minval_pos]:
                        minval_pos = i-k+1
                    if accu[i+1] - accu[minval_pos] >= 0:
                        delta = max(delta, (accu[i+1] - accu[minval_pos]) / (i+1 - minval_pos))
            return delta

        left, delta = min(nums), float("inf")
        while delta > 1e-5:
            delta = getDelta(left, nums, k)
            left += delta
        return left

s = Solution1()
nums = [1, 12, -5, -6, 50, 3]
K = 4
assert s.findMaxAverage(nums, K) == 12.75

See also:

https://leetcode.com/problems/maximum-average-subarray-ii